package analyses;

import graph.HasGraph;

import java.util.Iterator;
import java.util.ArrayList;
import java.util.PriorityQueue;


public class DijkstraShortestPath {
	//http://www.iti.fh-flensburg.de/lang/algorithmen/graph/dijkstra.htm
	//http://www.iti.fh-flensburg.de/lang/algorithmen/graph/shortest-paths.htm
	//http://en.wikipedia.org/wiki/Dijkstra_algorithm
	
	private HasGraph graph;

	private int s;
	
	private int e;

	private double[] dist;

	private int[] pred;

	private boolean[] tree;

	private double maxDist;

	
	
	public DijkstraShortestPath(HasGraph graph_, int s_, int e_) {
		graph = graph_;
		s = s_;
		e=e_;
		int n = graph.getNodesSize();
		dist = new double[n];
		pred = new int[n];
		tree = new boolean[n];
		for (int v = 0; v < n; v++) {
			dist[v] = Double.MAX_VALUE;
			pred[v] = -1;
			tree[v] = false;
		}
		computeShortestPath();
	}
	
	
	
	private void computeShortestPath() {
		maxDist = 0;
		int u, v;
		double d;
		Iterator<Integer> it;

		dist[s] = 0;
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();

		pq.offer(new Pair(0, s));

		while (!pq.isEmpty()&&!tree[e]) {
			
			u = pq.poll().index;
			
			if (!tree[u]) {
				tree[u] = true;
				it = graph.getNeighbourIterator(u);
				while (it.hasNext()) {
					v = it.next();
					d = dist[u] + graph.getWeight(u, v); 
					if (d < dist[v]) {
						if (maxDist < d) {
							maxDist = d;
						}
						dist[v] = d;
						pred[v] = u;
						pq.offer(new Pair(d, v));
					}
				}
			}
			
		}
	}

	// distance from node v to startNode
	public double getDistance() {
		return dist[e];
	}

	// predecessor to the node v from tree of shortestpaths
	public int getPredecessor(int v) {
		return pred[v];
	}

//	 sequenze of nodes form node v to startnode from tree of shortestpaths
	public ArrayList<Integer> getShortestPath() {
		int v=e;
		ArrayList<Integer> p = new ArrayList<Integer>();
		while (v != -1) {
			p.add(v);
			v = getPredecessor(v);
		}
		return p;
	}

	

	private class Pair implements Comparable {
		double value;

		int index;

		public Pair(double value, int index) {
			this.value = value;
			this.index = index;
		}

		public int compareTo(Object arg0) {
			// TODO Auto-generated method stub
			return Double.compare(value, ((Pair) arg0).value);
		}

	}
}
